//给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。 
//
// 注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。 
//
// 
//
// 示例 1: 
//
// 
//输入: s = "anagram", t = "nagaram"
//输出: true
// 
//
// 示例 2: 
//
// 
//输入: s = "rat", t = "car"
//输出: false 
//
// 
//
// 提示: 
//
// 
// 1 <= s.length, t.length <= 5 * 10⁴ 
// s 和 t 仅包含小写字母 
// 
//
// 
//
// 进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？ 
// Related Topics 哈希表 字符串 排序 👍 591 👎 0


import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * [0242]有效的字母异位词-ValidAnagram
 * <p>
 * 算法: 排序后比较-一个哈希表
 * <br>
 * 时间复杂度: O(nlogn)
 * <br>
 * 空间复杂度: O(logn)
 * <p>
 * 知识点:
 * <br>
 * 1. int 不能和 null 做比较, 否则 NPE    <br>
 * 2. 两个哈希表是否可以优化为一个哈希表    <br>
 * 3. 数组比HashMap效率高 5 倍左右    <br>
 * 4. 无法优化的时候, 可以从限定入参范围优化
 *
 * @author yonxao
 * @since 2022-06-01 15:44:07
 */
class ValidAnagram {
    @SuppressWarnings("all")
//leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isAnagram(String s, String t) {
            int length = s.length();
            if (length != t.length()) {
                return false;
            }

            char[] sa = s.toCharArray(); // space n, JAVA 中字符串是不可变的, 所以需要开辟额外空间拷贝字符串;
            // 这一部分空间可以忽略, 因为其他语言字符串可变或者形参就是 char[], 就可以省略, 依赖于语言和形参
            char[] ta = t.toCharArray(); // space n
            Arrays.sort(sa);  // time nlogn   space logn
            Arrays.sort(ta);  // time nlogn   space logn
            return Arrays.equals(sa, ta); // time n
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        String s = "anagram", t = "nagaram";
        String s2 = "rat", t2 = "car";
        System.out.println(isAnagram(s, t));
        System.out.println(isAnagram(s2, t2));

    }

    /**
     * 算法: 两个哈希表
     * <br>
     * 时间复杂度: O(3n) = O(n)
     * <br>
     * 空间复杂度: O(2n) = O(n)
     * <p>
     * 知识点: int 不能和 null 做比较, 否则 NPE
     * <br>
     */
    public static boolean first(String s, String t) {
        int n = s.length();
        if (n != t.length()) {
            return false;
        }

        Map<Character, Integer> map1 = new HashMap<>(); // space n

        for (int i = 0; i < n; i++) { // time n
            char c = s.charAt(i);
            Integer count = map1.getOrDefault(c, 0) + 1;
            map1.put(c, count);
        }

        Map<Character, Integer> map2 = new HashMap<>(); // space n
        for (int i = 0; i < n; i++) { // time n
            char c = t.charAt(i);
            Integer count = map2.getOrDefault(c, 0) + 1;
            map2.put(c, count);
        }

        for (Map.Entry<Character, Integer> entry : map1.entrySet()) { // time n
            // int 不能和 null 做比较, 否则 NPE
            if (!entry.getValue().equals(map2.get(entry.getKey()))) {
                return false;
            }
        }

        return true;
    }


    /**
     * 算法: 一个哈希表
     * <br>
     * 时间复杂度: O(2n) = O(n)
     * <br>
     * 空间复杂度: O(n)
     * <p>
     * 知识点: 两个哈希表优化为一个哈希表
     * <br>
     */
    public static boolean isAnagram(String s, String t) {
        int length = s.length();
        if (length != t.length()) {
            return false;
        }

        Map<Character, Integer> map = new HashMap<>(); // space n
        for (int i = 0; i < length; i++) { // time n
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        for (int i = 0; i < length; i++) { // time n
            char c = t.charAt(i);
            int count = map.getOrDefault(c, 0) - 1;
            if (count < 0) {
                return false;
            } else {
                map.put(c, count);
            }
        }
        return true;
    }


    /**
     * 算法: 排序后比较
     * <br>
     * 时间复杂度: O(2nlogn+n) = O(nlogn)
     * <br>
     * 空间复杂度: O(2logn) = O(logn), 忽略拷贝字符串所使用的空间
     * <p>
     * 知识点: 数组比HashMap效率高 5 倍左右
     * <br>
     */
    public static boolean isAnagram2(String s, String t) {
        int length = s.length();
        if (length != t.length()) {
            return false;
        }

        char[] sa = s.toCharArray(); // space n, JAVA 中字符串是不可变的, 所以需要开辟额外空间拷贝字符串;
        // 这一部分空间可以忽略, 因为其他语言字符串可变或者形参就是 char[], 就可以省略, 依赖于语言和形参
        char[] ta = t.toCharArray(); // space n
        Arrays.sort(sa);  // time nlogn   space logn
        Arrays.sort(ta);  // time nlogn   space logn
        return Arrays.equals(sa, ta); // time n
    }


    /**
     * 算法: 数组模拟哈希表, 参数只能是小写字母
     * <br>
     * 时间复杂度: O(2n) = O(n)
     * <br>
     * 空间复杂度: O(2n+26) = O(n); 忽略拷贝字符串所使用的空间, O(S), S为入参字符集大小
     * <p>
     * 知识点: 无法优化的时候, 可以从限定入参范围优化
     * <br>
     */
    public boolean isAnagram3(String s, String t) {
        int[] record = new int[26]; // space 26

        for (char c : s.toCharArray()) { // space n time n
            record[c - 'a'] += 1;
        }

        for (char c : t.toCharArray()) { // space n time n
            record[c - 'a'] -= 1;
        }

        for (int i = 0; i < 26; i++) { // time 26
            if (record[i] != 0) {
                return false;
            }
        }
        return true;
    }

}